﻿#pragma once
#include<iostream>
using namespace std;
#include<vector>
#include<map>
#include<queue>
#include<functional>
#include"UnionFindSet.h"

namespace matrix
{
	//V代表顶点，W代表边，Max_W代表边的默认权重 默认是无向图
	template <class V, class W, W Max_W = INT_MAX, bool Direction = false>
	class Graph
	{
		typedef Graph<V, W, Max_W, Direction> Self;
	public:
		Graph() = default;
		//构造图
		Graph(const V* vertexs, size_t n)
		{
			_vertexs.reserve(n);
			_matrix.resize(n);
			for (size_t i = 0; i < n; ++i)
			{
				_vertexs.emplace_back(vertexs[i]);
				_vIndexMap[vertexs[i]] = i;
				_matrix[i].resize(n, INT_MAX);
			}
			//每个顶点认为和自身是联通的，权值为0
			/*for (size_t i = 0; i < _matrix.size(); ++i)
			{
				for (size_t j = 0; j < _matrix[i].size(); ++j)
				{
					if (i == j)
					{
						_matrix[i][j] = 0;
					}
				}
			}*/
		}

		//得到顶点对应的下标
		size_t GetVertexIndex(const V& v)
		{
			auto it = _vIndexMap.find(v);
			if (it != _vIndexMap.end())
			{
				return it->second;
			}
			else
			{
				string s("顶点不存在");
				throw(s);
			}
		}

		//利用顶点下标构造边
		void _AddEdge(size_t srci, size_t dsti, W weight)
		{
			//无向图
			if (Direction == false)
			{
				_matrix[srci][dsti] = weight;
				_matrix[dsti][srci] = weight;
			}
			//有向图
			else
			{
				_matrix[srci][dsti] = weight;
			}
		}

		//利用顶点构造边
		void AddEdge(const V& src, const V& dst, W weight)
		{
			size_t i = GetVertexIndex(src);
			size_t j = GetVertexIndex(dst);
			_AddEdge(i, j, weight);
		}


		//广度优先遍历
		void BFS(const V& v)
		{
			size_t n = _vertexs.size();
			int srci = GetVertexIndex(v);

			queue<int> q;
			vector<bool> visited(n, false);
			q.push(srci);
			visited[srci] = true;
			while (!q.empty())
			{
				int front = q.front();
				cout << front << ":" << _vertexs[front] << endl;
				for (size_t i = 0; i < n; ++i)
				{
					if (_matrix[front][i] != Max_W)
					{
						if (visited[i] == false)
						{
							q.push(i);
							visited[i] = true;
						}
					}
				}
				q.pop();
			}
		}

		//广度优先遍历->层序遍历
		void BFSLevel(const V& v)
		{
			size_t n = _vertexs.size();
			int srci = GetVertexIndex(v);

			queue<int> q;
			vector<bool> visited(n, false);
			q.push(srci);
			visited[srci] = true;
			int levelsize = q.size();
			while (!q.empty())
			{
				for (size_t i = 0; i < levelsize; ++i)
				{
					int front = q.front();
					cout << front << ":" << _vertexs[front] << " ";
					for (size_t i = 0; i < n; ++i)
					{
						if (_matrix[front][i] != Max_W)
						{
							if (visited[i] == false)
							{
								q.push(i);
								visited[i] = true;
							}
						}
					}
					q.pop();
				}
				levelsize = q.size();
				cout << endl;
			}
		}

		void _DFS(const V& v, vector<bool>& visited)
		{
			size_t n = _vertexs.size();
			int srci = GetVertexIndex(v);
			visited[srci] = true;
			cout << _vertexs[srci] << endl;
			for (size_t i = srci; i < n; ++i)
			{
				if (_matrix[srci][i] != Max_W && visited[i] == false)
				{
					_DFS(_vertexs[i], visited);
				}
			}
		}
		void DFS(const V& v)
		{
			vector<bool> visited(_vertexs.size(), false);
			_DFS(v, visited);
		}

		struct Edge
		{
			size_t _srci;
			size_t _dsti;
			W _weight;
			Edge(int srci, int dsti, const W& weight)
				:_srci(srci)
				, _dsti(dsti)
				, _weight(weight)
			{}
			bool operator>(const Edge& e) const
			{
				return _weight > e._weight;
			}
		};
		typedef struct Edge Edge;

		//最小生成树-Kruskal算法
		W Kruskal(Self& minTree)
		{
			size_t n = _vertexs.size();
			minTree._vertexs = _vertexs;
			minTree._vIndexMap = _vIndexMap;
			minTree._matrix.resize(n);
			for (size_t i = 0; i < n; ++i)
			{
				minTree._matrix[i].resize(n, Max_W);
			}
			//先用一个优先级队列将边按权值从小到大排列
			priority_queue<Edge, vector<Edge>, greater<Edge>> pq;
			for (size_t i = 0; i < n; ++i)
			{
				for (size_t j = 0; j < n; ++j)
				{
					//无向图，只入一半的边进队列，另一半重复了
					if (_matrix[i][j] != Max_W && i < j)
					{
						pq.push(Edge(i, j, _matrix[i][j]));
					}
				}
			}
			int size = 0;
			UnionFindSet ufs(n);
			W total = W();
			//下面利用贪心策略依次从队列中取出边
			while (!pq.empty())
			{
				Edge min = pq.top();
				pq.pop();
				if (!ufs.Inset(min._srci, min._dsti))
				{
					//cout << _vertexs[min._srci] << "->" << _vertexs[min._dsti] <<" " << min._weight << endl;
					//可以添加的边
					minTree._AddEdge(min._srci, min._dsti, min._weight);
					//将两个顶点放在一个集合
					ufs.Union(min._srci, min._dsti);
					++size;
					total += min._weight;
				}
				else
				{
					//cout<<"构成环: "<< _vertexs[min._srci] << "->" << _vertexs[min._dsti]<<" "<<min._weight << endl;
				}
			}
			if (size == n - 1)
			{
				cout << "边的权值和为: " << total << endl;
				return total;
			}
			else
			{
				return W();
			}
		}

		//最小生成树-Prim算法
		W  Prim(Self& minTree, const V& src)
		{
			size_t n = _vertexs.size();
			minTree._vertexs = _vertexs;
			minTree._vIndexMap = _vIndexMap;
			minTree._matrix.resize(n);
			for (size_t i = 0; i < n; ++i)
			{
				minTree._matrix[i].resize(n, Max_W);
			}
			size_t srci = GetVertexIndex(src);
			vector<bool> X(n, false);
			vector<bool> Y(n, true);
			X[srci] = true;
			Y[srci] = false;
			priority_queue<Edge, vector<Edge>, greater<Edge>> pq;
			//把起点srci与Y集合相连的所有的边全部入队列
			for (size_t i = 0; i < n; ++i)
			{
				if (_matrix[srci][i] != Max_W)
				{
					pq.push(Edge(srci, i, _matrix[srci][i]));
				}
			}

			size_t size = 0;
			W total = W();
			while (!pq.empty())
			{
				Edge min = pq.top();
				pq.pop();
				//边的两个顶点不能同时在X集合
				if (X[min._dsti])
				{
					//cout << "构成环: " << _vertexs[min._srci] << "->" << _vertexs[min._dsti] << " " << min._weight << endl;
				}
				else
				{
					minTree._AddEdge(min._srci, min._dsti, min._weight);
					X[min._dsti] = true;
					Y[min._dsti] = false;
					//cout << _vertexs[min._srci] << "->" << _vertexs[min._dsti] << " " << min._weight << endl;
					++size;
					total += min._weight;
					if (size == n - 1)
					{
						break;
					}
					//继续把新增加的X集合的点与Y集合相连的所有边入队列
					for (size_t i = 0; i < n; ++i)
					{
						if (_matrix[min._dsti][i] != Max_W && Y[i])
						{
							pq.push(Edge(min._dsti, i, _matrix[min._dsti][i]));
						}
					}
				}

			}
			if (size == n - 1)
			{
				cout << "边的权值和为: " << total << endl;
				return total;
			}
			else
			{
				return W();
			}
		}

		void PrintShortPath(const V& src, const vector<W>& dist, const vector<int>& pPath)
		{
			size_t n = _vertexs.size();
			int srci = GetVertexIndex(src);
			for (size_t i = 0; i < n; ++i)
			{
				if (i != srci)
				{
					vector<int> path;
					size_t parenti = i;
					while (parenti != srci)
					{
						path.push_back(parenti);
						parenti = pPath[parenti];
					}
					path.push_back(srci);
					reverse(path.begin(), path.end());

					for (auto& index : path)
					{
						cout << _vertexs[index] << "->";
					}
					cout << "路径权值和为：" << dist[i] << endl;
				}
			}
		}
		void Dijkstra(const V& src, vector<W>& dist, vector<int>& pPath)
		{
			size_t n = _vertexs.size();
			int srci = GetVertexIndex(src);
			dist.resize(n, Max_W);
			pPath.resize(n, -1);
			dist[srci] = 0;
			pPath[srci] = srci;
			//已经确定的最短路径的集合
			vector<bool> S(n, false);
			for (size_t i = 0; i < n; ++i)
			{
				int u = 0;
				W min = Max_W;
				for (size_t j = 0; j < n; ++j)
				{
					//该顶点不在已经确定最短路径的顶点集合并且路径小于src到该顶点最新路径
					if (S[j] == false && dist[i] < min)
					{
						u = i;
						min = dist[u];
					}
				}
				S[u] = true;
				//找出顶点后 从该顶点松弛操作，依次更新其他顶点的最短路径
				for (size_t v = 0; v < n; ++v)
				{
					if (S[v] == false && dist[u] + _matrix[u][v] < dist[v] && _matrix[u][v] != Max_W)
					{
						dist[v] = min + _matrix[u][v];
						pPath[v] = u;
					}
				}

			}
		}

		//最短路径 可以处理负权路径
		bool BellmanFord(const V& src, vector<W>& dist, vector<int>& pPath)
		{
			size_t n = _vertexs.size();
			int srci = GetVertexIndex(src);
			dist.resize(n, Max_W);
			pPath.resize(n, -1);
			dist[srci] = W();
			pPath[srci] = srci;
			for (size_t k = 0; k < n; ++k)
			{
				bool update = false;
				cout << "第" << k << "次更新" << endl;
				for (size_t i = 0; i < n; ++i)
				{
					for (size_t j = 0; j < n; ++j)
					{
						if (_matrix[i][j] != Max_W && dist[i] + _matrix[i][j] < dist[j])
						{
							update = true;
							dist[j] = dist[i] + _matrix[i][j];
							pPath[j] = i;
						}
					}
				}
				if (!update)
					break;
			}
			//处理负权回路
			for (size_t i = 0; i < n; ++i)
			{
				for (size_t j = 0; j < n; ++j)
				{
					if (_matrix[i][j] != Max_W && dist[i] + _matrix[i][j] < dist[j])
					{
						return false;
					}
				}
			}
			return true;
		}

		void FloydWarshall(vector<vector<W>>& vvdist, vector<vector<int>>& vvpPath)
		{
			size_t n = _vertexs.size();
			vvdist.resize(n);
			vvpPath.resize(n);
			for (size_t i = 0; i < n; ++i)
			{
				vvdist[i].resize(n, Max_W);
				vvpPath[i].resize(n, -1);
			}

			//先更新直接相连的点的最短路径
			for (size_t i = 0; i < n; ++i)
			{
				for (size_t j = 0; j < n; ++j)
				{
					if (_matrix[i][j] != Max_W)
					{
						vvdist[i][j] = _matrix[i][j];
						vvpPath[i][j] = i;
					}
					if (i == j)
					{
						vvdist[i][j] = 0;
					}
				}
			}

			//每个节点都可能成为中间的k节点 需要全都遍历一边
			for (size_t k = 0; k < n; ++k)
			{
				//下面开始更新最短路径
				for (size_t i = 0; i < n; ++i)
				{
					for (size_t j = 0; j < n; ++j)
					{
						//中间经过了k节点  i->k k->j
						if (vvdist[i][k] != Max_W && vvdist[k][j] != Max_W && vvdist[i][k] + vvdist[k][j] < vvdist[i][j])
						{
							//更新i-> j 的最短路径
							vvdist[i][j] = vvdist[i][k] + vvdist[k][j];
							//更新j 节点的父亲节点 注意这里不是k 有可能k->j中间也经过了其他节点 因为这里k和j并一定是直接相连
							vvpPath[i][j] = vvpPath[k][j];
						}
					}
				}


				// 打印权值和路径矩阵观察数据
				for (size_t i = 0; i < n; ++i)
				{
					for (size_t j = 0; j < n; ++j)
					{
						if (vvdist[i][j] == Max_W)
						{
							//cout << "*" << " ";
							printf("%3c", '*');
						}
						else
						{
							//cout << vvDist[i][j] << " ";
							printf("%3d", vvdist[i][j]);
						}
					}
					cout << endl;
				}
				cout << endl;

				for (size_t i = 0; i < n; ++i)
				{
					for (size_t j = 0; j < n; ++j)
					{
						//cout << vvParentPath[i][j] << " ";
						printf("%3d", vvpPath[i][j]);
					}
					cout << endl;
				}
				cout << "=================================" << endl;
			}
		}




		void Print()
		{

			// 打印顶点和下标映射关系
			for (size_t i = 0; i < _vertexs.size(); ++i)
			{
				cout << _vertexs[i] << "-" << i << " ";
			}
			cout << endl << endl;
			cout << " ";
			for (size_t i = 0; i < _vertexs.size(); ++i)
			{
				cout << i << " ";
			}
			cout << endl;
			// 打印矩阵
			for (size_t i = 0; i < _matrix.size(); ++i)
			{
				cout << i << " ";
				for (size_t j = 0; j < _matrix[i].size(); ++j)
				{
					if (_matrix[i][j] != Max_W)
						cout << _matrix[i][j] << " ";
					else
						cout << "#" << " ";
				}
				cout << endl;
			}
			cout << endl << endl;
			// 打印所有的边
			for (size_t i = 0; i < _matrix.size(); ++i)
			{
				for (size_t j = 0; j < _matrix[i].size(); ++j)
				{
					if (i < j && _matrix[i][j] != Max_W)
					{
						cout << _vertexs[i] << "-" << _vertexs[j] << ":" <<
							_matrix[i][j] << endl;
					}
				}
			}
		}

		void MyPrint()
		{

			for (size_t i = 0; i < _vertexs.size(); ++i)
			{
				cout << "[" << _vertexs[i] << "]" << "->" << _vIndexMap[_vertexs[i]] << endl << endl;
			}

			cout << "    ";
			//打印一下横着的顶点
			for (size_t i = 0; i < _vertexs.size(); ++i)
			{
				cout << _vertexs[i] << "   ";
			}
			cout << endl << endl;
			for (size_t i = 0; i < _matrix.size(); ++i)
			{
				//先打印下竖着的顶点
				cout << _vertexs[i] << "   ";
				for (size_t j = 0; j < _matrix[i].size(); ++j)
				{
					if (_matrix[i][j] == INT_MAX)
					{
						cout << "@" << "   ";
					}
					else
					{
						cout << _matrix[i][j] << "   ";
					}
				}
				cout << endl << endl;;
			}
		}
	private:
		map<V, size_t> _vIndexMap;  //顶点和下标的映射关系
		vector<V> _vertexs; // 顶点集合
		vector<vector<W>> _matrix; //存储顶点之间边的关系的邻接矩阵
	};
}


namespace linktable
{
	template<class W>
	struct Edge
	{
		int _srci;
		int _dsti;
		W _weight;
		Edge<W>* _next;

		Edge(int srci,int dsti,const W& weight)
			:_srci(srci)
			,_dsti(dsti)
			,_weight(weight)
			,_next(nullptr)
		{}
	};

	//V代表顶点，W代表边，Max_W代表边的默认权重 默认是无向图
	template <class V, class W, bool Direction = false>
	class Graph
	{
		typedef struct Edge<W> Edge;
	public:
		Graph() = default;
		//构造图
		Graph(const V* vertexs, size_t n)
		{
			_vertexs.reserve(n);
			_tables.resize(n);
			for (size_t i = 0; i < n; ++i)
			{
				_vertexs.emplace_back(vertexs[i]);
				_vIndexMap[vertexs[i]] = i;
			}
		}

		//得到顶点对应的下标
		size_t GetVertexIndex(const V& v)
		{
			auto it = _vIndexMap.find(v);
			if (it != _vIndexMap.end())
			{
				return it->second;
			}
			else
			{
				string s("顶点不存在");
				throw(s);
			}
		}

		//添加边
		void AddEdge(const V& src, const V& dst, W weight)
		{
			size_t srci = GetVertexIndex(src);
			size_t dsti = GetVertexIndex(dst);
			//有向图
			Edge* eg = new Edge(srci,dsti,weight);
			eg->_next = _tables[srci];
			_tables[srci] = eg;
			//无向图
			if (Direction == false)
			{
				Edge* eg = new Edge(dsti,srci, weight);
				eg->_next = _tables[dsti];
				_tables[dsti] = eg;
			}
		}


		//出边表
		void Print()
		{
			for (size_t i = 0; i < _tables.size(); ++i)
			{
				cout << "[" << i << "]" << _vertexs[i] << " ";
				Edge* cur = _tables[i];
				while (cur)
				{
					cout <<"->"<< "["<<_vertexs[cur->_dsti] << cur->_weight <<"]" << " ";
					cur = cur->_next;
				}
				cout << "->nullptr" << endl;
			}
		}
	
		////入边表
		//void Print1()
		//{
		//	for (size_t i = 0; i < _tables.size(); ++i)
		//	{
		//		cout << "[" << i << "]" << _vertexs[i] << " ";
		//		Edge* cur = _tables[i];
		//		while (cur)
		//		{
		//			cout << "<-" << "[" << _vertexs[cur->_srci] << cur->_weight << "]" << " ";
		//			cur = cur->_next;
		//		}
		//		cout << "<-nullptr" << endl;
		//	}
		//}

	private:
		map<V, size_t> _vIndexMap;  //顶点和下标的映射关系
		vector<V> _vertexs; // 顶点集合
		vector<Edge*> _tables; //存储顶点之间边的关系的邻接矩阵
	};
}